﻿//  二维数组及相关习题（二分查找法，两边向中间）
//数组的行可以省略，但是略不能省略
//中间数的查找很关键（防止数据溢出）int mid = left + (rigght - left) / 2
#define _CRT_SECURE_NO_WARNINGS 1
//#include <stdio.h>
//
//int main()
//{
//	int i = 0;
//	int arr[3][5] = { 0 };
//	for (i = 0;i < 3;i++)
//	{
//		int j = 0;
//		for (j = 0;j < 5;j++)//需要明白循环嵌套的时候的输入，是不是需要两个scanf？？？
//		{
//			scanf("%d", &arr[i][j]);
//		}
//	
//	}
//	for (i = 0;i < 3;i++)
//	{
//		int j = 0;
//		for (j = 0;j < 5;j++)
//		{
//			printf("%d\n", arr[i][j]);//这里不能取地址！！！
//		}
//
//	}
//	return 0;
//}



//#include <stdio.h>
//
//int main()
//{
//	int i = 0;
//	int arr[3][5] = { 1,2,3,4,5,6,7,8,9 };
//	for (i = 0;i < 3;i++)
//	{
//		int j = 0;
//		for (j = 0;j < 5;j++)
//		{
//			printf("&arr[%d][%d] = %p\n", i, j, &arr[i][j]);
//		}
//
//	}
//	
//	return 0;
//}
//代码运行的结果说明：二维数组的存储是连续的！也就是说为什么可以省略行，但是不能省略列
//&arr[0][0] = 00000050EA79F618
//& arr[0][1] = 00000050EA79F61C
//& arr[0][2] = 00000050EA79F620
//& arr[0][3] = 00000050EA79F624
//& arr[0][4] = 00000050EA79F628
//& arr[1][0] = 00000050EA79F62C
//& arr[1][1] = 00000050EA79F630
//& arr[1][2] = 00000050EA79F634
//& arr[1][3] = 00000050EA79F638
//& arr[1][4] = 00000050EA79F63C
//& arr[2][0] = 00000050EA79F640
//& arr[2][1] = 00000050EA79F644
//& arr[2][2] = 00000050EA79F648
//& arr[2][3] = 00000050EA79F64C
//& arr[2][4] = 00000050EA79F650


//不同编程语言中数组变长情况发展历程不同。

//在C语言中，C99标准开始支持变长数组（VLA）。
// 含义：变长数组是其大小可在运行时确定的数组，即数组大小可由变量指定，
// 而非编译期的常量表达式。
// 例如  int n = 5; int arr[n]; 
//  n  是变量，这样就创建了大小为5的数组  arr 。


//          vs不支持，但是可以更换编译器

//#include <stdio.h>
//
//int main()
//{
//	int n = 10;
//	int arr3[n];
//	//输入数据
//	int i = 0;
//
//	for (i = 0; i < 5; i++)
//	{
//		scanf("%d", &arr3[i]);
//	}
//	for (i = 0; i < 5; i++)
//	{
//		printf("%d ", arr3[i]);
//	}
//	return 0;
//}


//#include <stdio.h>
//
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int arr3[n];
//	int i = 0;
//	for (i = 0;i < n; i++)
//	{
//		scanf("%d", arr3);//           记得加地址操作符
//	}
//	for (i = 0;i < n; i++)
//	{
//	printf("%d",arr3);
//	}
//
//	return 0;
//}//               输入地址操作符的操作
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);//输入n
//	int arr3[n];
//	//输入数据
//	int i = 0;
//
//	for (i = 0; i < n; i++)
//	{
//		scanf("%d", &arr3[i]);
//	}
//	for (i = 0; i < n; i++)
//	{
//		printf("%d ", arr3[i]);
//	}
//	return 0;
//}
//


//welcome to bit!!!!!!!
//#####################
//w###################!
//we#################!!
//wel###############!!!
//....
//welcome to bit!!!!!!!
//#include <time.h>
//#include <string.h>
//#include <stdio.h>
//#include <stdlib.h>
//#include <windows.h>
//int main()
//{
//	char arr1[] = "welcome bit!!!";
//	char arr2[] = "##############";
//	int left = 0;
//	int right = strlen(arr1) - 1;
//	while (left <= right)
//	{
//		arr2[left] = arr1[left];
//		arr2[right] = arr1[right];
//		printf("%s\n", arr2);
//		left++;
//		right--;
//		Sleep(1000);
//		system("cls");
// 
//	}
//	printf("%s", arr2);
//	return 0;
//
//}

//   汉字不能直接运行出来，理由如下
//
//#include <time.h>
//#include <string.h>
//#include <stdio.h>
//#include <stdlib.h>
//#include <windows.h>
//int main()
//{
//	char str[] = "姚国蓉加油加油";
//	char arr2[] = "##############";
//	int left = 0;
//	int right = strlen(str) - 1;
//	while (left <= right)
//	{
//		arr2[left] = str[left];
//		arr2[right] = str[right];
//		printf("%s\n", arr2);
//		left++;
//		right--;
//		Sleep(1000);
//		system("cls");
//
//	}
//	printf("加油呀，小笨蛋");
//	return 0;
//
//}
//在C语言中，汉字不是传统意义上的字符（character）。
//
//C语言中基本的字符类型是 char ，它通常用来存储一个字节的ASCII码字符，
//范围有限，无法直接存储汉字。
//汉字一般占多个字节，常见的UTF - 8编码中，一个汉字通常占用3个字节；GBK
//编码一个汉字占用2个字节。
//
//不过可以使用数组来存储汉字序列，比如 char str[] = "你好"; 
//这里 str 数组可以存储汉字字符串 ，
//字符串中的每个汉字按相应编码规则以字节序列形式存储在内存中
//此外，宽字符类型 wchar_t  可以用来处理不同编码下的字符，
//包括汉字，例如 wchar_t wc = L'好'; ，
//使用宽字符常量时需要在前面加 L 前缀

//一组依次升序的数字中查找
//二分查找法，折半查找法

//1.找出数组的中间元素
//2.使用中间的元素和要找的元素进行比较，然后看数据在哪个元素

#include <stdio.h>
//
//int main()
//{
//	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
//	int n = 0;
//	scanf("%d", &n);
//	int i = 0;
//	int flag = 0;//没找到
//	int sz = sizeof(arr) / sizeof(arr[0]);
//	for (i = 0;i < sz;i++)
//	{
//		if (arr[i] == n)
//		{
//			printf("找到了，下标是%d\n", i);
//			flag = 1;
//			break;
//		}
//	}
//	if (flag == 0)
//		printf("找不到\n")；
//
//	return 0;
//}

//int main()
//{
//	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
//	int n = 0;//17
//	scanf("%d", &n);//我们要在数组arr中找到n中的数字
//	//折半查找/二分查找
//
//	int sz = sizeof(arr) / sizeof(arr[0]);
//	int left = 0;
//	int right = sz - 1;
//	int flag = 0;//找不到
//	while (left <= right)
//	{
//		//int mid = (left + right) / 2;
//		int mid = left + (right - left) / 2;
//		if (arr[mid] < n)
//		{
//			left = mid + 1;
//		}
//		else if (arr[mid] > n)
//		{
//			right = mid - 1;
//		}
//		else
//		{
//			printf("找到了，下标是:%d\n", mid);
//			flag = 1;
//			break;
//		}
//	}
//	if (flag == 0)
//		printf("找不到\n");
//	return 0;
//}

int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	int n = 0;//17
	scanf("%d", &n);//我们要在数组arr中找到n中的数字
	//折半查找/二分查找

	int sz = sizeof(arr) / sizeof(arr[0]);
	int left = 0;
	int right = sz - 1;
	int flag = 0;//找不到
	while (left <= right)
	{
		//int mid = (left + right) / 2;
		int mid = left + (right - left) / 2;
		if (arr[mid] < n)
		{
			left = mid + 1;
		}
		else if (arr[mid] > n)
		{
			right = mid - 1;
		}
		else
		{
			printf("找到了，下标是:%d\n", mid);
			flag = 1;
			break;
		}
	}
	if (flag == 0)
		printf("找不到\n");
	return 0;
}